/*
 * @Author: CB
 * @Date: 2023-01-09 17:35:41
 * @Descripttion: 简单的双向链表
 */


/** 双向链表上的节点 */
interface ILinkNode<T> {
    element: T;
    next: ILinkNode<T> | null;
    pre: ILinkNode<T> | null;
}


export class LinkList<T> {
    /** 链表第一个节点 */
    first: ILinkNode<T>;

    /** 链表最后一个节点 */
    last: ILinkNode<T>;

    private _size: number = 0

    constructor(element?: T) {
        if (element !== undefined) {
            const linkNode: ILinkNode<T> = {
                element: element,
                pre: null,
                next: null
            }
            this.first = linkNode;
            this.last = linkNode;
            this._size = 1;
        }
    }

    /** 链表大小 */
    get size() {
        return this._size;
    }

    /** 获取下标为 index 的节点 */
    get(index: number): T | null {
        return this.getNode(index)?.element;
    }

    /**
     * 给链表添加一个节点 默认添加在尾部
     * @param linkNode 新加的节点
     * @param inHead 是否是在头部添加
     */
    push(element: T, inHead: boolean = false) {
        let linkNode: ILinkNode<T> = {
            element: element,
            pre: null,
            next: null
        }

        if (this.first && this.last) {
            if (inHead) {
                linkNode.pre = null;
                linkNode.next = this.first;
                this.first.pre = linkNode;
                this.first = linkNode;
            } else {
                linkNode.pre = this.last;
                this.last.next = linkNode;
                this.last = linkNode;
            }
        } else {
            this.first = linkNode;
            this.last = linkNode;
        }
        this._size++;
    }

    /** 在节点后面添加节点 */
    pushAfterNode(element: T, node: ILinkNode<T>) {
        if (!element || !node) return;
        const next = node.next;
        let insertNode: ILinkNode<T> = {
            element: element,
            pre: node,
            next: next
        }
        node.next = insertNode;
        if (this.last === next) this.last = insertNode;
        if (next) next.pre = insertNode;
        this._size++;
    }

    /** 插入节点 */
    insert(element: T, index: number): boolean {
        if (index === this._size || this._size === 0) {
            this.push(element);
            return true;
        }

        const oldPreNode = this.getNode(index);
        if (!oldPreNode) {
            console.error('插入位置不合法: ', index, this._size);
            return false;
        }
        const newNode: ILinkNode<T> = {
            element: element,
            pre: oldPreNode.pre,
            next: oldPreNode
        }
        if (oldPreNode.pre) {
            oldPreNode.pre.next = newNode;
        } else {
            this.first = newNode;
        }
        this._size++;
        return true;
    }

    /** 删除第一个节点并返回 */
    shift(): T | null {
        if (this.first) {
            const result: ILinkNode<T> = {
                element: this.first.element,
                pre: null,
                next: null
            }
            const newHead = this.first.next;
            if (newHead) {
                newHead.pre = null;
            }
            this.first = newHead;
            if (!newHead) this.last = null;
            this._size--;
            return result.element;
        }
        return null;
    }

    /** 删除最后一个节点并返回 */
    pop(): T | null {
        if (this.last) {
            const result: ILinkNode<T> = {
                element: this.last.element,
                pre: null,
                next: null
            }
            const newLast = this.last.pre;
            if (newLast) {
                newLast.next = null;
                this.last = newLast;
            } else {
                this.first = null;
            }
            this._size--;
            return result.element;
        }
        return null;
    }

    /** 清理链表 */
    clear() {
        let node = this.first;
        while (node) {
            const next = node.next;
            node.pre = null;
            node.next = null;
            node = next;
        }
        this.first = null;
        this.last = null;
        this._size = 0;
    }

    /** 遍历链表 */
    forEach(func: (element: T, index: number) => void) {
        if (this._size === 0) return;
        let node = this.first;
        for (let i = 0; i < this._size; i++) {
            func(node.element, i);
            node = node.next;
        }
    }

    /** 根据下标获取节点 */
    private getNode(index: number): ILinkNode<T> | null {
        if (this._size === 0) return null;
        if (index < 0) index += this._size;
        if (index >= this._size || index < 0) return null;
        const halfIndex = this._size / 2;
        if (index < halfIndex) {
            //从前面开始找
            let node = this.first;
            for (let i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            //从后面开始找
            let node = this.last;
            const findCount = this._size - index - 1;
            for (let i = 0; i < findCount; i++) {
                node = node.pre;
            }
            return node;
        }
    }
}